/*
 * This program is free software; you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation; either version 2 of the License, or
 * (at your option) any later version.
 * 
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 * 
 * You should have received a copy of the GNU General Public License
 * along with this program; if not, write to the Free Software
 * Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
 */

/*
 * LAGDHillClimber.java
 * Copyright (C) 2005 Manuel Neubach
 * 
 */

package weka.classifiers.bayes.net.search.local;

import weka.classifiers.bayes.BayesNet;
import weka.core.Instances;
import weka.core.Option;
import weka.core.RevisionUtils;
import weka.core.Utils;

import java.util.Enumeration;
import java.util.Vector;

/**
 * <!-- globalinfo-start --> This Bayes Network learning algorithm uses a Look
 * Ahead Hill Climbing algorithm called LAGD Hill Climbing. Unlike Greedy Hill
 * Climbing it doesn't calculate a best greedy operation (adding, deleting or
 * reversing an arc) but a sequence of nrOfLookAheadSteps operations, which
 * leads to a network structure whose score is most likely higher in comparison
 * to the network obtained by performing a sequence of nrOfLookAheadSteps greedy
 * operations. The search is not restricted by an order on the variables (unlike
 * K2). The difference with B and B2 is that this hill climber also considers
 * arrows part of the naive Bayes structure for deletion.
 * <p/>
 * <!-- globalinfo-end -->
 * 
 * <!-- options-start --> Valid options are:
 * <p/>
 * 
 * <pre>
 * -L &lt;nr of look ahead steps&gt;
 *  Look Ahead Depth
 * </pre>
 * 
 * <pre>
 * -G &lt;nr of good operations&gt;
 *  Nr of Good Operations
 * </pre>
 * 
 * <pre>
 * -P &lt;nr of parents&gt;
 *  Maximum number of parents
 * </pre>
 * 
 * <pre>
 * -R
 *  Use arc reversal operation.
 *  (default false)
 * </pre>
 * 
 * <pre>
 * -N
 *  Initial structure is empty (instead of Naive Bayes)
 * </pre>
 * 
 * <pre>
 * -mbc
 *  Applies a Markov Blanket correction to the network structure, 
 *  after a network structure is learned. This ensures that all 
 *  nodes in the network are part of the Markov blanket of the 
 *  classifier node.
 * </pre>
 * 
 * <pre>
 * -S [BAYES|MDL|ENTROPY|AIC|CROSS_CLASSIC|CROSS_BAYES]
 *  Score type (BAYES, BDeu, MDL, ENTROPY and AIC)
 * </pre>
 * 
 * <!-- options-end -->
 * 
 * @author Manuel Neubach
 * @version $Revision: 1.7 $
 */
public class LAGDHillClimber extends HillClimber {

	/** for serialization */
	static final long serialVersionUID = 7217437499439184344L;

	/** Number of Look Ahead Steps **/
	int m_nNrOfLookAheadSteps = 2;

	/** Number of Good Operations per Step **/
	int m_nNrOfGoodOperations = 5;

	/**
	 * search determines the network structure/graph of the network
	 * 
	 * @param bayesNet
	 *            the network
	 * @param instances
	 *            the data to use
	 * @throws Exception
	 *             if something goes wrong
	 */
	protected void search(BayesNet bayesNet, Instances instances)
			throws Exception {
		int k = m_nNrOfLookAheadSteps; // Number of Look Ahead Steps
		int l = m_nNrOfGoodOperations; // Number of Good Operations per step
		lookAheadInGoodDirectionsSearch(bayesNet, instances, k, l);
	} // search

	/**
	 * lookAheadInGoodDirectionsSearch determines the network structure/graph of
	 * the network with best score according to LAGD Hill Climbing
	 * 
	 * @param bayesNet
	 *            the network
	 * @param instances
	 *            the data to use
	 * @param nrOfLookAheadSteps
	 * @param nrOfGoodOperations
	 * @throws Exception
	 *             if something goes wrong
	 */
	protected void lookAheadInGoodDirectionsSearch(BayesNet bayesNet,
			Instances instances, int nrOfLookAheadSteps, int nrOfGoodOperations)
			throws Exception {
		System.out.println("Initializing Cache");
		initCache(bayesNet, instances);

		while (nrOfLookAheadSteps > 1) {
			System.out.println("Look Ahead Depth: " + nrOfLookAheadSteps);
			boolean legalSequence = true;
			double sequenceDeltaScore = 0;
			Operation[] bestOperation = new Operation[nrOfLookAheadSteps];

			bestOperation = getOptimalOperations(bayesNet, instances,
					nrOfLookAheadSteps, nrOfGoodOperations);
			for (int i = 0; i < nrOfLookAheadSteps; i++) {
				if (bestOperation[i] == null) {
					legalSequence = false;
				} else {
					sequenceDeltaScore += bestOperation[i].m_fDeltaScore;
				}
			}
			while (legalSequence && sequenceDeltaScore > 0) {
				System.out.println("Next Iteration..........................");
				for (int i = 0; i < nrOfLookAheadSteps; i++) {
					performOperation(bayesNet, instances, bestOperation[i]);
				}
				bestOperation = getOptimalOperations(bayesNet, instances,
						nrOfLookAheadSteps, nrOfGoodOperations);
				sequenceDeltaScore = 0;
				for (int i = 0; i < nrOfLookAheadSteps; i++) {
					if (bestOperation[i] != null) {
						System.out.println(bestOperation[i].m_nOperation + " "
								+ bestOperation[i].m_nHead + " "
								+ bestOperation[i].m_nTail);
						sequenceDeltaScore += bestOperation[i].m_fDeltaScore;
					} else {
						legalSequence = false;

					}
					System.out.println("DeltaScore: " + sequenceDeltaScore);
				}
			}
			--nrOfLookAheadSteps;
		}

		/** last steps with greedy HC **/
		Operation oOperation = getOptimalOperation(bayesNet, instances);
		while ((oOperation != null) && (oOperation.m_fDeltaScore > 0)) {
			performOperation(bayesNet, instances, oOperation);
			System.out.println("Performing last greedy steps");
			oOperation = getOptimalOperation(bayesNet, instances);
		}
		// free up memory
		m_Cache = null;
	} // lookAheadInGoodDirectionsSearch

	/**
	 * getAntiOperation determines the Operation, which is needed to cancel
	 * oOperation
	 * 
	 * @param oOperation
	 *            Operation to cancel
	 * @return antiOperation to oOperation
	 * @throws Exception
	 *             if something goes wrong
	 */
	protected Operation getAntiOperation(Operation oOperation) throws Exception {
		if (oOperation.m_nOperation == Operation.OPERATION_ADD)
			return (new Operation(oOperation.m_nTail, oOperation.m_nHead,
					Operation.OPERATION_DEL));
		else {
			if (oOperation.m_nOperation == Operation.OPERATION_DEL)
				return (new Operation(oOperation.m_nTail, oOperation.m_nHead,
						Operation.OPERATION_ADD));
			else {
				return (new Operation(oOperation.m_nHead, oOperation.m_nTail,
						Operation.OPERATION_REVERSE));
			}
		}
	} // getAntiOperation

	/**
	 * getGoodOperations determines the nrOfGoodOperations best Operations,
	 * which are considered for the calculation of an optimal operationsequence
	 * 
	 * @param bayesNet
	 *            Bayes network to apply operation on
	 * @param instances
	 *            data set to learn from
	 * @param nrOfGoodOperations
	 *            number of good operations to consider
	 * @return good operations to consider
	 * @throws Exception
	 *             if something goes wrong
	 **/
	protected Operation[] getGoodOperations(BayesNet bayesNet,
			Instances instances, int nrOfGoodOperations) throws Exception {
		Operation[] goodOperations = new Operation[nrOfGoodOperations];
		for (int i = 0; i < nrOfGoodOperations; i++) {
			goodOperations[i] = getOptimalOperation(bayesNet, instances);
			if (goodOperations[i] != null) {
				m_Cache.put(goodOperations[i], -1E100);
			} else
				i = nrOfGoodOperations;
		}
		for (int i = 0; i < nrOfGoodOperations; i++) {
			if (goodOperations[i] != null) {
				if (goodOperations[i].m_nOperation != Operation.OPERATION_REVERSE) {
					m_Cache.put(goodOperations[i],
							goodOperations[i].m_fDeltaScore);
				} else {
					m_Cache.put(
							goodOperations[i],
							goodOperations[i].m_fDeltaScore
									- m_Cache.m_fDeltaScoreAdd[goodOperations[i].m_nHead][goodOperations[i].m_nTail]);
				}
			} else
				i = nrOfGoodOperations;
		}
		return goodOperations;
	} // getGoodOperations

	/**
	 * getOptimalOperations determines an optimal operationsequence in respect
	 * of the parameters nrOfLookAheadSteps and nrOfGoodOperations
	 * 
	 * @param bayesNet
	 *            Bayes network to apply operation on
	 * @param instances
	 *            data set to learn from
	 * @param nrOfLookAheadSteps
	 *            number of lood ahead steps to use
	 * @param nrOfGoodOperations
	 *            number of good operations to consider
	 * @return optimal sequence of operations in respect to nrOfLookAheadSteps
	 *         and nrOfGoodOperations
	 * @throws Exception
	 *             if something goes wrong
	 **/
	protected Operation[] getOptimalOperations(BayesNet bayesNet,
			Instances instances, int nrOfLookAheadSteps, int nrOfGoodOperations)
			throws Exception {
		if (nrOfLookAheadSteps == 1) { // Abbruch der Rekursion
			Operation[] bestOperation = new Operation[1];
			bestOperation[0] = getOptimalOperation(bayesNet, instances);
			return (bestOperation); // Abbruch der Rekursion
		} else {
			double bestDeltaScore = 0;
			double currentDeltaScore = 0;
			Operation[] bestOperation = new Operation[nrOfLookAheadSteps];
			Operation[] goodOperations = new Operation[nrOfGoodOperations];
			Operation[] tempOperation = new Operation[nrOfLookAheadSteps - 1];
			goodOperations = getGoodOperations(bayesNet, instances,
					nrOfGoodOperations);
			for (int i = 0; i < nrOfGoodOperations; i++) {
				if (goodOperations[i] != null) {
					performOperation(bayesNet, instances, goodOperations[i]);
					tempOperation = getOptimalOperations(bayesNet, instances,
							nrOfLookAheadSteps - 1, nrOfGoodOperations); // rekursiver
																			// Abstieg
					currentDeltaScore = goodOperations[i].m_fDeltaScore;
					for (int j = 0; j < nrOfLookAheadSteps - 1; j++) {
						if (tempOperation[j] != null) {
							currentDeltaScore += tempOperation[j].m_fDeltaScore;
						}
					}
					performOperation(bayesNet, instances,
							getAntiOperation(goodOperations[i]));
					if (currentDeltaScore > bestDeltaScore) {
						bestDeltaScore = currentDeltaScore;
						bestOperation[0] = goodOperations[i];
						for (int j = 1; j < nrOfLookAheadSteps; j++) {
							bestOperation[j] = tempOperation[j - 1];
						}
					}
				} else
					i = nrOfGoodOperations;
			}
			return (bestOperation);
		}
	} // getOptimalOperations

	/**
	 * Sets the max number of parents
	 * 
	 * @param nMaxNrOfParents
	 *            the max number of parents
	 */
	public void setMaxNrOfParents(int nMaxNrOfParents) {
		m_nMaxNrOfParents = nMaxNrOfParents;
	}

	/**
	 * Gets the max number of parents.
	 * 
	 * @return the max number of parents
	 */
	public int getMaxNrOfParents() {
		return m_nMaxNrOfParents;
	}

	/**
	 * Sets the number of look-ahead steps
	 * 
	 * @param nNrOfLookAheadSteps
	 *            the number of look-ahead steps
	 */
	public void setNrOfLookAheadSteps(int nNrOfLookAheadSteps) {
		m_nNrOfLookAheadSteps = nNrOfLookAheadSteps;
	}

	/**
	 * Gets the number of look-ahead steps
	 * 
	 * @return the number of look-ahead step
	 */
	public int getNrOfLookAheadSteps() {
		return m_nNrOfLookAheadSteps;
	}

	/**
	 * Sets the number of "good operations"
	 * 
	 * @param nNrOfGoodOperations
	 *            the number of "good operations"
	 */
	public void setNrOfGoodOperations(int nNrOfGoodOperations) {
		m_nNrOfGoodOperations = nNrOfGoodOperations;
	}

	/**
	 * Gets the number of "good operations"
	 * 
	 * @return the number of "good operations"
	 */
	public int getNrOfGoodOperations() {
		return m_nNrOfGoodOperations;
	}

	/**
	 * Returns an enumeration describing the available options.
	 * 
	 * @return an enumeration of all the available options.
	 */
	public Enumeration listOptions() {
		Vector newVector = new Vector();

		newVector.addElement(new Option("\tLook Ahead Depth", "L", 2,
				"-L <nr of look ahead steps>"));
		newVector.addElement(new Option("\tNr of Good Operations", "G", 5,
				"-G <nr of good operations>"));

		Enumeration enm = super.listOptions();
		while (enm.hasMoreElements()) {
			newVector.addElement(enm.nextElement());
		}
		return newVector.elements();
	} // listOptions

	/**
	 * Parses a given list of options. Valid options are:
	 * <p>
	 * 
	 * <!-- options-start --> Valid options are:
	 * <p/>
	 * 
	 * <pre>
	 * -L &lt;nr of look ahead steps&gt;
	 *  Look Ahead Depth
	 * </pre>
	 * 
	 * <pre>
	 * -G &lt;nr of good operations&gt;
	 *  Nr of Good Operations
	 * </pre>
	 * 
	 * <pre>
	 * -P &lt;nr of parents&gt;
	 *  Maximum number of parents
	 * </pre>
	 * 
	 * <pre>
	 * -R
	 *  Use arc reversal operation.
	 *  (default false)
	 * </pre>
	 * 
	 * <pre>
	 * -N
	 *  Initial structure is empty (instead of Naive Bayes)
	 * </pre>
	 * 
	 * <pre>
	 * -mbc
	 *  Applies a Markov Blanket correction to the network structure, 
	 *  after a network structure is learned. This ensures that all 
	 *  nodes in the network are part of the Markov blanket of the 
	 *  classifier node.
	 * </pre>
	 * 
	 * <pre>
	 * -S [BAYES|MDL|ENTROPY|AIC|CROSS_CLASSIC|CROSS_BAYES]
	 *  Score type (BAYES, BDeu, MDL, ENTROPY and AIC)
	 * </pre>
	 * 
	 * <!-- options-end -->
	 * 
	 * @param options
	 *            the list of options as an array of strings
	 * @throws Exception
	 *             if an option is not supported
	 */
	public void setOptions(String[] options) throws Exception {
		String sNrOfLookAheadSteps = Utils.getOption('L', options);
		if (sNrOfLookAheadSteps.length() != 0) {
			setNrOfLookAheadSteps(Integer.parseInt(sNrOfLookAheadSteps));
		} else {
			setNrOfLookAheadSteps(2);
		}

		String sNrOfGoodOperations = Utils.getOption('G', options);
		if (sNrOfGoodOperations.length() != 0) {
			setNrOfGoodOperations(Integer.parseInt(sNrOfGoodOperations));
		} else {
			setNrOfGoodOperations(5);
		}

		super.setOptions(options);
	} // setOptions

	/**
	 * Gets the current settings of the search algorithm.
	 * 
	 * @return an array of strings suitable for passing to setOptions
	 */
	public String[] getOptions() {
		String[] superOptions = super.getOptions();
		String[] options = new String[9 + superOptions.length];
		int current = 0;

		options[current++] = "-L";
		options[current++] = "" + m_nNrOfLookAheadSteps;

		options[current++] = "-G";
		options[current++] = "" + m_nNrOfGoodOperations;

		// insert options from parent class
		for (int iOption = 0; iOption < superOptions.length; iOption++) {
			options[current++] = superOptions[iOption];
		}

		// Fill up rest with empty strings, not nulls!
		while (current < options.length) {
			options[current++] = "";
		}
		return options;
	} // getOptions

	/**
	 * This will return a string describing the search algorithm.
	 * 
	 * @return The string.
	 */
	public String globalInfo() {
		return "This Bayes Network learning algorithm uses a Look Ahead Hill Climbing algorithm called LAGD Hill Climbing."
				+ " Unlike Greedy Hill Climbing it doesn't calculate a best greedy operation (adding, deleting or reversing an arc) "
				+ "but a sequence of nrOfLookAheadSteps operations, which leads to a network structure whose score is most likely "
				+ "higher in comparison to the network obtained by performing a sequence of nrOfLookAheadSteps greedy operations. "
				+ "The search is not restricted by an order "
				+ "on the variables (unlike K2). The difference with B and B2 is that this hill "
				+ "climber also considers arrows part of the naive Bayes structure for deletion.";
	} // globalInfo

	/**
	 * @return a string to describe the Number of Look Ahead Steps option.
	 */
	public String nrOfLookAheadStepsTipText() {
		return "Sets the Number of Look Ahead Steps. 'nrOfLookAheadSteps = 2' means that all network structures in a "
				+ "distance of 2 (from the current network structure) are taken into account for the decision which arcs to add, "
				+ "remove or reverse. 'nrOfLookAheadSteps = 1' results in Greedy Hill Climbing.";
	} // nrOfLookAheadStepsTipText

	/**
	 * @return a string to describe the Number of Good Operations option.
	 */
	public String nrOfGoodOperationsTipText() {
		return "Sets the Number of Good Operations per Look Ahead Step. 'nrOfGoodOperations = 5' means that for the next "
				+ "Look Ahead Step only the 5 best Operations (adding, deleting or reversing an arc) are taken into account for the "
				+ "calculation of the best sequence consisting of nrOfLookAheadSteps operations.";
	} // nrOfGoodOperationsTipText

	/**
	 * Returns the revision string.
	 * 
	 * @return the revision
	 */
	public String getRevision() {
		return RevisionUtils.extract("$Revision: 1.7 $");
	}

} // LAGDHillClimber
